/*
 *   项目名称：leetcode
 *   文件名称：com.xiaolon.leetcode.seq.SeqDemo
 *
 *   创建人：  ZHOU XIAO LONG
 *   创建日期：2024/7/15
 *
 */
package com.xiaolon.leetcode.seq;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;

import java.sql.SQLOutput;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

/**
 * 类描述： SeqDemo
 **/
public class SeqDemo {

    @Test
    public void testCheckInlusion(){
        // 判断字符串str2是否包含字符串str1的变位词
        System.out.println("判断字符串str2是否包含字符串str1的变位词");
        String str2 = "abc";
        String str1 = "bca";
        System.out.println(checkInlusion(str2, str1));
    }

    @Test
    public void testIsPalindrome(){
        System.out.println("判断字符串str是否为回文字符串");
        String str1 = "aba";
        System.out.println(str1 + ": "+isPalindrome(str1));
        // 可能包含空格等字符
        String str2 = "ab c ba!";
        System.out.println(str2 + ": "+isPalindrome(str2));
    }

    @Test
    public void testValidPalindrome(){
        System.out.println("判断最多删除一个字符串能否构成回文串");
        String str1 = "abca";
        System.out.println(validPalindrome(str1));

        String str2 = "aba";
        System.out.println(validPalindrome(str2));

        String str3 = "abcd";
        System.out.println(validPalindrome(str3));
    }

    @Test
    public void testKMP(){
        System.out.println("KMP算法");
        String text1 = "abcd";
        String pattern1 = "cd";
        System.out.println(kmp(text1, pattern1));

        String text2 = "abcdabab";
        String pattern2 = "abab";
        System.out.println(kmp(text2, pattern2));
    }

    /**
     * 模式匹配，比较字串word中是否包含字符pattern
     * 成功返回位置
     * 失败返回-1
     * @param text
     * @param pattern
     * @return
     */
    public static int kmp(String text, String pattern){
        // kmp算法核心是加速字符串比较速度
        int m = text.length();
        int n = pattern.length();

        int[] next = getNext(pattern);
        System.out.println("next: "+Arrays.toString(next));

        int i=0,j=0;
        while (i<m && j<n){
            if(j==-1 || text.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
            if(j == n)return i-j;
        }
        return -1;
    }

    /**
     * 求pattern字符串的next数组
     * @param pattern
     * @return
     */
    public static int[] getNext(String pattern){
        // 当前位置不匹配，下一个应该匹配的位址
        int n = pattern.length();
        int[] next = new int[n];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j < n-1){
            if(k==-1 || pattern.charAt(j) == pattern.charAt(k)){
                k++;
                j++;
                next[j] = k;
            }else{
                k = next[k];
            }
        }
        return next;
    }


    /**
     * 判断最多删除一个字符串能否构成回文串
     * @param str
     * @return
     */
    public static boolean validPalindrome(String str){
        // 1. 找出位址
        // 2. 跳过当前位置
        // 3. 比较剩余字符是否为回文串
        int start=0, end = str.length()-1;

        // 先定位出字符位置
        for(;start<str.length()/2;start++,end--){
            if(str.charAt(start) != str.charAt(end)) break;
        }
        // 如果字符串长度为奇数，且指针到中间位置=>仍为回文串
        // 否则找出不同字符，并跳过该位置，剩余字符仍为回文串
        return start==str.length()/2 || isPalindrome(str, start+1, end) || isPalindrome(str, start, end-1);
    }

    /**
     * 判断字符串[start, end]是否为回文串
     * @param str
     * @param start
     * @param end
     * @return
     */
    public static boolean isPalindrome(String str, int start, int end){
        while(start<end){
            if(str.charAt(start) != str.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }


    /**
     * 判断字符串str是否为回文字符串
     * @param str
     */
    public static boolean isPalindrome(String str){
        // 双指针
        int first=0,last=str.length()-1;
        while(first<last){
            char ch1 = str.charAt(first);
            char ch2 = str.charAt(last);
            if(!Character.isLetterOrDigit(ch1)) first++;
            else if(!Character.isLetterOrDigit(ch2)) last--;
            else{
                ch1 = Character.toLowerCase(ch1);
                ch2 = Character.toLowerCase(ch2);
                if(ch1 != ch2)return false;
                first++;
                last--;
            }
        }
        return true;
    }

    /**
     * 判断字符串str2是否包含str1的变位词
     * @param str2
     * @param str1
     * @return
     */
    public static boolean checkInlusion(String str2, String str1){
        int[] counts = new int[26];
        if(str2.length() < str1.length())return false;
        for (int i = 0; i < str1.length(); i++) {
            counts[str1.charAt(i) - 'a']++;
            counts[str2.charAt(i) - 'a']--;
        }

        if(allZero(counts)) return true;
        for (int i = str1.length(); i < str2.length(); i++) {
            counts[str2.charAt(i-str1.length()) - 'a']++;
            counts[str2.charAt(i) - 'a']--;
            if(allZero(counts)) return true;

        }
        return false;
    }

    public static boolean allZero(int[] counts){
        for (int count : counts) {
            if(count!=0) return false;
        }
        return true;
    }


}